package PTA.练习04;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-11-16
 * Time: 21:11
 */
import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] list = new int[size];//输入树的节点总数
        for (int i = 0; i < size; i++) {
            list[i] = sc.nextInt();
        }
        BinarySearchTree bst = new BinarySearchTree();
        bst.create(list);
        int insertSize = sc.nextInt();//插入的次数
        for (int i = 0; i < insertSize; i++) {
            bst.insert(sc.nextInt());//插入的节点
        }
        int removeSize = sc.nextInt();//删除的次数
        for (int i = 0; i < removeSize; i++) {
            bst.remove(sc.nextInt());//删除的节点
        }
        int searchId = sc.nextInt();
        bst.search(searchId);//查找
        System.out.println(bst.getHeight());//高度
    }
}
class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val; // 正确赋值
        left = right = null;
    }
}

class BinarySearchTree {
    // 根据给定的整数数组创建一个二叉搜索树
    TreeNode head = new TreeNode(Integer.MIN_VALUE); // 使用极小值作为占位符，避免影响插入逻辑

    public void create(int[] list) {
        if (list.length > 0) {
            head.val = list[0]; // 通常不使用 head.val 存储实际数据，这里仅为初始化方便
            TreeNode rootNode = new TreeNode(list[0]); // 创建真正的根节点
            head.left = rootNode; // 将占位符的左子节点指向真正的根
            for (int i = 1; i < list.length; i++) {
                insert(list[i]);
            }
        }
    }

    // 查找值为 key 的节点，查找成功之后输出该节点存在，不成功输出该节点不存在。
    public void search(int key) {
        TreeNode node = head.left; // 从真正的根节点开始搜索
        while (node != null) {
            if (key == node.val) {
                System.out.println("该节点存在");
                return;
            } else if (key < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        System.out.println("该节点不存在");
    }

    // 插入一个值为 key 的节点，若树中已存在该节点则输出不能插入重复元素!
    public boolean insert(int key) {
        TreeNode node = head.left; // 从真正的根节点开始
        TreeNode parent = null;
        while (node != null) {
            parent = node;
            if (node.val == key) {
                System.out.println("不能插入重复元素!");
                return false;
            } else if (key < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        TreeNode newNode = new TreeNode(key);
        if (key < parent.val) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        return true;
    }

    // 删除某个值为 key 的节点，如果树中不存在该节点则输出不存在该元素!
    // 如果删除的节点是中间节点，那么在存在右子树的情况下，让右子树中最小的节点上升为被删除的节点（简化处理）
    public void remove(int key) {
        TreeNode node = head.left;
        TreeNode parent = null;
        while (node != null && node.val != key) {
            parent = node;
            if (key < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        if (node == null) {
            System.out.println("不存在该元素!");
            return;
        }
        if (node.left == null && node.right == null) { // 叶子节点
            if (parent.left == node) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (node.left == null) { // 只有一个右子节点
            if (parent.left == node) {
                parent.left = node.right;
            } else {
                parent.right = node.right;
            }
        } else if (node.right == null) { // 只有一个左子节点
            if (parent.left == node) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } else { // 有两个子节点，找到右子树中的最小节点替代
            TreeNode minNode = findMin(node.right);
            node.val = minNode.val; // 用右子树最小节点的值替换当前节点的值
            remove(minNode.val); // 删除右子树中的最小节点（此时它成为叶子节点）
        }
    }

    // 找到树中的最小节点
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 最后输出树的高度，只有根节点时高度为 1
    public int getHeight() {
        return maxDepth(head.left); // 从真正的根节点开始计算高度
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
}